1. Field of the Invention
The present invention relates to integrated circuit design and layout.
2. State of the Art
Traditional cell-based integrated circuit design follows several steps. The first step is designing the logical gate-level circuit that implements the function to be realized by the circuit (referred to as logic design or logic synthesis, of which logic optimizations are a key part). The next step is placing the gates (or cells) in a physical layout, and the final step is routing the interconnection between the cells. With increasing dominance of interconnection delays and area in circuits implemented in deep submicron technologies, this approach is proving to be no longer viable. The problem is that, during the logic optimization stage, the interconnection is not known yet, and thus the dominant part of the area and the delay cannot be considered.
Attempts to overcome this problem have considered alternating logic synthesis and placement and routing, with "back annotation" of the interconnect information to the subsequent logic synthesis steps. Referring to FIG. 1, showing traditional cell-based design flow, a logic design phase is followed by a cell placement phase and then a routing phase. Following the routing phase, interconnection data is back annotated. The logic design, cell placement and routing phases are then repeated. This cycle is continued until, during the routing phase, the design is successfully routed. The problem with this method is that the logic synthesis steps that consider the back annotation information cannot guarantee to fix problems that prevent routing without introducing additional problems due to the modifications made to the circuit gates and topology. There results a large number of iterations between logic synthesis and subsequent place and route, with the possibility of the process never converging.
An alternative approach is to consider placement information during logic optimization. In this methodology, sometimes termed "placement aware synthesis," placement information is made available in varying degrees during logic optimization, i.e. some placement is done as part of logic synthesis (sometimes referred to in the industry as just synthesis). Logic optimization uses this placement information to estimate the effect of the interconnects on the delay and the area of the circuit. Thus logic optimization attempts to accurately model the interconnect delay and area that might result during a placement step. However, it may result in a placed circuit that cannot be routed using the area resources provided by the placement step. The inability to route the resulting placed circuit results in modifications to the placement, consequently nullifying the interconnection information used during logic optimization.
A circuit that has been placed but cannot be routed subject to the available area constraints is not realizable. Additional routing resources must be created to enable the routing. There results an increase in circuit area and possibly delay, since the wires may now need to go through longer paths.
Placement algorithms are limited in how they can place cells by the timing constraints placed on the design. The timing constraints may result in certain parts of the design being very congested in terms of the wiring (or interconnection) resources needed to connect the cells in those parts of the circuit. It would be possible to relieve the congestion if somehow the cells in the congested area were to be moved apart. However, moving the cells apart may result in an increase in the interconnection delays, which in turn may result in a violation of the timing constraints. Thus a situation results where it is possible to have acceptable timing slacks or acceptable congestion but not both.
The paper by Villarubia and Hojat (ICCD 97) proposes integrated logic optimization and placement. However, the proposed methodology alternates placement and logic optimization and does not consider the impact of the logic optimizations on subsequent placement steps.